﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.ReverseList
{
    class MainProkect
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(CountAndSay(9));
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(2);
            ListNode listNode3 = new ListNode(3);
            ListNode listNode4 = new ListNode(4);
            ListNode listNode5 = new ListNode(5);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            listNode4.next = listNode5;
           
            ListNode listNode = ReverseList(listNode1);
            while (listNode!=null)
            {
                Console.WriteLine("## = " + listNode.val);
                listNode = listNode.next;
            }
            Console.ReadKey();
        }
        public static ListNode ReverseList(ListNode head)
        {
            if (head==null)
                return null;
            Stack<ListNode> nodeStack = new Stack<ListNode>();
            ListNode processNode = head;
            ListNode reverseHead = null;
            ListNode reverseProcessHead = null;
            while (processNode!=null)
            {
                //入栈
                nodeStack.Push(processNode);
                processNode = processNode.next;
            }

            reverseHead = nodeStack.Pop();
            reverseProcessHead = reverseHead;
            while (nodeStack.Count>0)
            {
                ListNode listNode =  nodeStack.Pop();
                listNode.next = null;
                reverseProcessHead.next = listNode;
                reverseProcessHead = reverseProcessHead.next;
            }

            return reverseHead;
        }
    }
}
